//包含min函数的栈
class Solution {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public void push(int node) {
        stack1.push(node);
        if(stack2.empty() || node <= stack2.peek()) {
            stack2.push(node);
        }
    }

    public void pop() {
        int top = stack1.pop();
        if(top == stack2.peek()) {
            stack2.pop();
        }
    }

    public int top() {
        return stack1.peek();
    }

    public int min() {
        return stack2.peek();
    }
}


//用两个栈实现队列
class Solution2 {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(!stack2.empty()) return stack2.pop();

        while(!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}


public class Top_101 {

    //BM2 链表内指定区间反转
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head == null || m == n) return head;

        ListNode cur = head;
        ListNode prev = head;
        //1. 走完这个循环，newhead为第m个结点的前驱结点，cur为开始反转结点
        for(int i = m-1; i > 0; i--) {
            prev = cur;
            cur = cur.next;
        }
        //2. 开始反转指定区间的链表，若cur为空且count>n，则要求反转区间异常，返回null
        ListNode newhead = cur;
        ListNode tmp = cur;     //保存反转区间链表的最后一个结点的引用
        cur = cur.next;
        for(int i = n-1;i >= m ; i--) {
            ListNode curNext = cur.next;
            cur.next = newhead;
            newhead = cur;
            cur = curNext;
        }
        //3. 将反转的链表的最后一个结点与后面结点相连
        tmp.next = cur;

        //4. 若从1位置开始反转，则返回newhead；不然则需将反转链表之间的结点与反转链表
        //相连，并返回head结点
        if(m == 1) {
            return newhead;
        }
        prev.next = newhead;
        return head;
    }


    //BM1 反转链表
    public ListNode ReverseList (ListNode head) {
        if(head == null) return null;

        ListNode newhead = new ListNode(head.val);
        head = head.next;
        while(head != null) {
            ListNode next = head.next;
            head.next = newhead;
            newhead = head;
            head = next;;
        }
        return newhead;
    }



    //BM3 链表中的节点每k个一组翻转
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || k == 1) return head;

        ListNode slow = head;
        ListNode fast = head;
        ListNode newHead = new ListNode(-1);
        ListNode tail = newHead;       //记录 最新链表的 尾结点
        while(fast != null) {
            int i = k;
            for(; fast != null && i > 0; i--) {
                fast = fast.next;
            }
            // 此次遍历的链表的长度 < k , 即剩下的链表不用翻转
            if(i > 0) {
                tail.next = slow;
            }
            // 目前有 k 个结点需要反转
            if(i == 0) {
                ListNode flag = slow;       //记录此段链表结点翻转完成后的最后一个结点
                ListNode tmphead = slow;
                slow = slow.next;
                while(slow != fast) {
                    ListNode slowNext = slow.next;
                    slow.next = tmphead;
                    tmphead = slow;
                    slow = slowNext;
                }
                tail.next = tmphead;
                tail = flag;
                //如果整个链表的长度是 k 的整数倍，则 将 tail结点 的next 置为空
                if(fast == null) {
                    tail.next = null;
                }
            }
        }
        return newHead.next;
    }



    //BM23 二叉树的前序遍历
    private void preOrder(List<Integer> list, TreeNode root) {
        if(root == null) return;
        list.add(root.val);
        preOrder(list, root.left);
        preOrder(list, root.right);
    }
    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preOrder(list, root);

        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }




    //BM34 判断是不是二叉搜索树
    public boolean isValidBST (TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        //记录 栈中上一次弹出 的结点
        TreeNode preTop = null;
        while(root != null || !stack.empty()) {
            if(root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode top = stack.pop();
                if(preTop == null) {
                    preTop = top;
                } else {
                    if(preTop.val > top.val) {
                        return false;
                    } else {
                        preTop = top;
                    }
                }
                root = top.right;
            }
        }
        return true;
    }




    //NC16 对称的二叉树
    public boolean isSymmetrical (TreeNode pRoot) {
            if(pRoot == null) return true;

            return isSymmetricalChild(pRoot.left, pRoot.right);
        }
    private boolean isSymmetricalChild(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) return true;
        if(leftTree == null || rightTree == null) return false;

        if(leftTree.val == rightTree.val) {
            return isSymmetricalChild(leftTree.left, rightTree.right) && isSymmetricalChild(leftTree.right, rightTree.left);
        } else {
            return false;
        }
    }



    //BM5 合并k个已排序的链表
    class IntCmp implements Comparator<ListNode> {
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        PriorityQueue<ListNode> minHead = new PriorityQueue<>(new IntCmp());

        for(int i = 0; i < lists.size(); i++) {
            if(lists.get(i) != null) {
                minHead.offer(lists.get(i));
            }
        }
        ListNode newHead = new ListNode(-1);
        ListNode tail = newHead;
        while(minHead.size() > 0) {
            ListNode top = minHead.poll();
            tail.next = top;
            tail = top;
            top = top.next;
            if(top != null) {
                minHead.offer(top);
            }
        }

        return newHead.next;
    }



    //BM27 按之字形顺序打印二叉树
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(pRoot == null) return ret;

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        queue1.offer(pRoot);
        int flag = 0;   //flag 为0 表示 stack 为空， 为1表示 stack 不为空
        while(!queue1.isEmpty() || !queue2.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            if(!queue1.isEmpty()) {
                while(!queue1.isEmpty()) {
                    TreeNode top = queue1.poll();
                    if(top.left != null) {
                        queue2.offer(top.left);
                        stack.push(top.left);
                    }
                    if(top.right != null) {
                        queue2.offer(top.right);
                        stack.push(top.right);
                    }
                    list.add(top.val);
                }

            } else if(!queue2.isEmpty()) {
                while(!queue2.isEmpty()) {
                    TreeNode top = queue2.poll();
                    if(top.left != null) queue1.offer(top.left);
                    if(top.right != null) queue1.offer(top.right);
                    list.add(stack.pop().val);
                }
            }
            ret.add(list);
        }
        return ret;

    }



    //BM6 判断链表中是否有环
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;

        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        return false;
    }



    //BM7 链表中环的入口结点
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null) return null;

        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if(fast == null || fast.next == null) return null;

        fast = pHead;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }




    //BM11 链表相加(二)
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        ListNode newHead1 = null;
        ListNode newHead2 = null;
        // 1. 将 两个链表利用 头插法 进行反转
        while (head1 != null || head2 != null) {
            if (head1 != null) {
                ListNode next = head1.next;
                head1.next = newHead1;
                newHead1 = head1;
                head1 = next;
            }
            if (head2 != null) {
                ListNode next = head2.next;
                head2.next = newHead2;
                newHead2 = head2;
                head2 = next;
            }
        }
        //将两个链表 头节点的值相加， 并进行头插法反转
        ListNode newhead = null;
        int extra = 0;      // 记录 进位的数值
        while(newHead1 != null || newHead2 != null) {
            int sum = extra;
            if(newHead1 != null) sum += newHead1.val;
            if(newHead2 != null) sum += newHead2.val;
            ListNode tmp = new ListNode(sum % 10);
            tmp.next = newhead;
            newhead = tmp;
            extra = sum / 10;

            if(newHead1 != null) newHead1 = newHead1.next;
            if(newHead2 != null) newHead2 = newHead2.next;
        }

        if(extra > 0) {
            ListNode tmp = new ListNode(extra);
            tmp.next = newhead;
            newhead = tmp;
        }
        return newhead;

    }





    //BM46 最小的K个数
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        if(input.length == 0 || k == 0) return ret;

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
             public int compare(Integer o1, Integer o2) {
                 return o2 - o1;
             }
         });
        for(int i = 0; i < input.length; i++) {
            if(i < k) {
                maxHeap.offer(input[i]);
            }else {
                if(input[i] < maxHeap.peek()) {
                    maxHeap.poll();
                    maxHeap.offer((input[i]));
                }
            }
        }
        while(!maxHeap.isEmpty()) {
            ret.add(maxHeap.poll());
        }
        return ret;
    }




    //BM50 两数之和
    public int[] twoSum (int[] numbers, int target) {
        int[] ret = new int[2];
        // Key记录 target 减去 一个加数的值， Value 记录这个加数的下标
        Map<Integer, Integer> map = new HashMap<>();
        map.put(target - numbers[0], 0);
        for(int i = 1; i < numbers.length; i++) {
            if(map.get(numbers[i]) != null) {
                ret[0] = map.get(numbers[i]) + 1;
                ret[1] = i + 1;
            }else {
                map.put(target - numbers[i], i);
            }
        }

        return ret;
    }


    //链表的奇偶重排
    public ListNode oddEvenList (ListNode head) {
        if(head == null) return null;

        ListNode oddHead = new ListNode(-1);
        ListNode evenHead = new ListNode(-1);
        ListNode tail1 = oddHead;
        ListNode tail2 = evenHead;
        int k = 1;
        while(head != null) {
            if(k % 2 == 1) {
                tail1.next = head;
                tail1 = head;
            } else {
                tail2.next = head;
                tail2 = head;
            }
            k++;
            head = head.next;
        }
        tail1.next = evenHead.next;
        tail2.next = null;
        return oddHead.next;

    }



    //寻找第K大
    public int findKth (int[] a, int n, int K) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for(int i = 0; i < n; i++) {
            if(i < K) {
                minHeap.add(a[i]);
            } else {
                if(a[i] > minHeap.peek()) {
                    minHeap.remove();
                    minHeap.add(a[i]);
                }
            }
        }
        return minHeap.remove();
    }



    //缺失的第一个正整数
    public int minNumberDisappeared (int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                set.add(nums[i]);
            }
        }
        int min = 1;
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(min)) min++;
        }
        return min;
    }




    //数组中只出现一次的两个数字
    public int[] FindNumsAppearOnce (int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }

        int[] ret = new int[2];
        int k = 0;
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                ret[k++] = nums[i];
            }
            if(k == 2) break;
        }
        Arrays.sort(ret);
        return ret;
    }



    //单链表的排序
    public ListNode sortInList (ListNode head) {
        if(head == null) return null;

        // 1. 把入堆结点 以val值 建立成为一个 小根堆
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        while(head != null) {
            minHeap.offer(head);
            head = head.next;
        }

        // 2. 堆顶元素依次出队，尾插法构建一个单链表
        head = new ListNode(-1);
        ListNode tail = head;
        while(!minHeap.isEmpty()) {
            tail.next = minHeap.poll();
            tail = tail.next;
        }
        tail.next = null;
        return head.next;
    }





    //删除链表的倒数第n个节点
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head == null) return null;

        ListNode slow = head;
        ListNode fast = head;
        ListNode PreSlow = head;
        int i = n - 1;
        while(i > 0) {
            fast = fast.next;
            i--;
        }
        while(fast.next != null) {
            PreSlow = slow;
            slow = slow.next;
            fast = fast.next;
        }

        if(PreSlow == slow) {
            head = head.next;
        } else {
            PreSlow.next = slow.next;
        }

        return head;
    }





    //链表中倒数最后k个结点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null || k == 0) return null;

        ListNode fast = pHead;
        ListNode slow = pHead;
        int i = k - 1;
        for(; fast != null && i > 0; i--) {
            fast = fast.next;
        }
        if(i > 0 || fast == null) return null;

        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }



    //数组中出现次数超过一半的数字
    public int MoreThanHalfNum_Solution (int[] numbers) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < numbers.length; i++) {
            if(map.get(numbers[i]) == null) {
                map.put(numbers[i], 1);
            } else {
                int val = map.get(numbers[i]);
                map.put(numbers[i], val + 1);
            }
            if(map.get(numbers[i]) > numbers.length / 2) return numbers[i];
        }

        return -1;
    }



    //二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null) return false;

        sum -= root.val;
        if(root.left == null && root.right == null && sum == 0) {
            return true;
        }

        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }



    //合并二叉树
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1 == null) return t2;
        if(t2 == null) return t1;

        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }



    //二叉树的最大深度
    public int maxDepth (TreeNode root) {
        if(root == null) return 0;

        int lH = maxDepth(root.left);
        int rH = maxDepth(root.right);
        return lH>rH?lH+1:rH+1;
    }



    //二维数组中的查找
    public boolean Find (int target, int[][] array) {
        if(array.length == 0 || array[0].length == 0) return false;

        // n 表示当前 行下标， m 表示 列下标
        int n = array.length - 1;
        int m = 0;
        while(n >= 0 && m < array[0].length) {
            if(array[n][m] == target) return true;
            if(array[n][m] > target) {
                n--;
            } else {
                m++;
            }
        }
        return false;
    }




    //二分查找-I
    public int search (int[] nums, int target) {
        if(nums.length == 0) return -1;

        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            if(nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }



    //删除有序链表中重复的元素-I
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(prev.val != cur.val) {
                prev = cur;
                cur = cur.next;
            } else {
                while(cur != null && prev.val == cur.val) {
                    cur = cur.next;
                }
                // 此时 cur 一定指向与 prev非重复的值的结点  或 null
                prev.next = cur;
                prev = cur;
                if(cur != null) cur = cur.next;
            }
        }
        return head;
    }



    //判断一个链表是否为回文结构
    public boolean isPail (ListNode head) {
        if(head == null || head.next == null) return true;

        ListNode fast = head;
        ListNode slow = head;
        ListNode prevSlow = null;
        // 1. 让 slow 定位到链表的中间位置
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            prevSlow = slow;
            slow = slow.next;
        }
        // 2. 从 slow 开始往后 反转链表
        ListNode tmp = prevSlow;
        while(slow != null) {
            ListNode slowNext = slow.next;
            slow.next = tmp;
            tmp = slow;
            slow = slowNext;
        }
        // 3. 将tmp 与 head 按链表顺序依次遍历检查
        while(head != tmp ) {
            if(head.val != tmp.val) return false;
            if(head.next == tmp) return true;
            head = head.next;
            tmp = tmp.next;
        }
        return true;
    }




    // 两个链表的第一个公共结点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode longList = pHead1;
        ListNode shortList = pHead2;
        int len1 = 0;
        int len2 = 0;
        while(longList != null || shortList != null) {
            if(longList != null) {
                len1++;
                longList = longList.next;
            }
            if(shortList != null) {
                len2++;
                shortList = shortList.next;
            }
        }

        int len = len1 - len2;         // 记录两个链表的长度差
        longList = pHead1;
        shortList = pHead2;
        if(len < 0) {
            len = -len;
            longList = pHead2;
            shortList = pHead1;
        }

        for(int i = len; i > 0; i--) {
            longList = longList.next;
        }
        while(shortList != null) {
            if(shortList == longList) return shortList;
            shortList = shortList.next;
            longList = longList.next;
        }
        return null;
    }



    //判断是不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode front = queue.poll();
            if(front != null) {
                queue.offer(front.left);
                queue.offer(front.right);
            } else {
                //如果当前出队节点为null，若剩下元素存在非空结点，则该二叉树不是完全二叉树
                while(!queue.isEmpty()) {
                    TreeNode tmp = queue.poll();
                    if(tmp != null) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
